|
|
Automata with a Limited Number of Pure Pushdowns
Soukup, Ondřej ; Zemek, Petr (referee) ; Meduna, Alexandr (advisor)
Pushdown automata with limited number of pure pushdowns are specialization of pure pushdown automata. Examination of their power is mainly focused on the view of combinatorics of words. In language defined by automata we introduce term of dependence, which denotes relation between parts of strings in language. It is shown, how the defined automata proceed on processing of dependencies. Then the relation between distribution of dependencies in language and required number of pushdowns is derived. Also is defined the infinite hierarchy of languages corresponding to automata in dependence on number of their pushdowns. At the end belonging of the class of languages defined by pushdown automata with limited number of pure pushdowns to Chomsky hierarchy of languages is studied, but it is discovered, that they do not correspond to Chomsky hierarchy. Based on this result it is proposed to study possible changes of models as a future development. Then the simulating program is created to illustrate features of examined automata.
|
|
| |
|
|
Squares in integer sequences
Hudcová, Barbora ; Holub, Štěpán (advisor) ; Bulín, Jakub (referee)
This work is based on an article which provides a construction of the first infinite word over a finite alphabet avoiding additive cubes. We construct other words with the same properties and we choose one of them to show the main idea of the proof that this word avoids additive cubes. 1
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
Title: Structure of equality sets Author: Jana Hadravová Department: Department of Algebra Supervisor: doc. Mgr. Štěpán Holub, Ph.D., Dept. of Algebra Abstract: Binary equality set of two morphisms g, h : ⌃⇤ ! A⇤ is a set of all words w over two-letter alphabet ⌃ satisfying g(w) = h(w). Elements of this set are called binary equality words. One of the important results of research on binary equality sets is the proof of the fact that each binary equality set is generated by at most two words provided that both morphisms g and h are non-periodic. Moreover, if a binary equality set is generated by exactly two words, then the structure of both generators, and therefore of the whole set, is uniquely given. This work presents the results of our research on the structure of binary equality sets with a single generator. Importantly, these generators can be decomposed into simpler structures. Generators which can not be further decomposed are called simple equality words. First part of the presented work describes the structure of simple equality words and introduces their detailed classification. The main result of the first part is a precise characterisation of su ciently large simple equality words. In the second part, the work describes the iterative process which transforms a general generator of a binary...
|
|
|
Squares in integer sequences
Hudcová, Barbora ; Holub, Štěpán (advisor) ; Bulín, Jakub (referee)
This work is based on an article which provides a construction of the first infinite word over a finite alphabet avoiding additive cubes. We construct other words with the same properties and we choose one of them to show the main idea of the proof that this word avoids additive cubes. 1
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
Title: Structure of equality sets Author: Jana Hadravová Department: Department of Algebra Supervisor: doc. Mgr. Štěpán Holub, Ph.D., Dept. of Algebra Abstract: Binary equality set of two morphisms g, h : ⌃⇤ ! A⇤ is a set of all words w over two-letter alphabet ⌃ satisfying g(w) = h(w). Elements of this set are called binary equality words. One of the important results of research on binary equality sets is the proof of the fact that each binary equality set is generated by at most two words provided that both morphisms g and h are non-periodic. Moreover, if a binary equality set is generated by exactly two words, then the structure of both generators, and therefore of the whole set, is uniquely given. This work presents the results of our research on the structure of binary equality sets with a single generator. Importantly, these generators can be decomposed into simpler structures. Generators which can not be further decomposed are called simple equality words. First part of the presented work describes the structure of simple equality words and introduces their detailed classification. The main result of the first part is a precise characterisation of su ciently large simple equality words. In the second part, the work describes the iterative process which transforms a general generator of a binary...
|
|
|
Quadratic word equations
Olšák, Miroslav ; Holub, Štěpán (advisor) ; Stanovský, David (referee)
The article discuses satisfiability of quadratic word equations. It reproduces results of Robson and Diekert and explores the question about simple exponential bound of the shortest solution of quadratic word equations. The positive answer to this question would mean NP completeness of satisfiability of quadratic word equations. The simple exponential bound hypothesis was not solved but some results were given: for example a smaller class of equations which needs to be investigated or a proposition saying that it is sufficient to prove a bound of the smallest variable. At the end of this work the behavior of a particular equations is shown and afterwards the duality of two concepts of quadratic word equations handling is explained. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
|
Kombinatorika hashovacích funkcí
Sýkora, Jiří ; Holub, Štěpán (advisor) ; Šaroch, Jan (referee)
In this thesis, we study hash functions. We focus mainly on the famous Merkle-Damg˚ard construction and its generalisation. We show that even this generalised construction is not resistant to multicollision attacks. Combinatorics on words plays a fundamental role in the construction of our attack. We prove that regularities unavoidably appear in long words with bounded number of symbol occurences. We present our original results concerning regularities in long words. We lower some earlier published estimates, thus reducing the comlexity of the attack. Our results show that generalised iterated hash functions are interesting rather from the theoretical than practical point of view. 1
|
|
|
Automata with a Limited Number of Pure Pushdowns
Soukup, Ondřej ; Zemek, Petr (referee) ; Meduna, Alexandr (advisor)
Pushdown automata with limited number of pure pushdowns are specialization of pure pushdown automata. Examination of their power is mainly focused on the view of combinatorics of words. In language defined by automata we introduce term of dependence, which denotes relation between parts of strings in language. It is shown, how the defined automata proceed on processing of dependencies. Then the relation between distribution of dependencies in language and required number of pushdowns is derived. Also is defined the infinite hierarchy of languages corresponding to automata in dependence on number of their pushdowns. At the end belonging of the class of languages defined by pushdown automata with limited number of pure pushdowns to Chomsky hierarchy of languages is studied, but it is discovered, that they do not correspond to Chomsky hierarchy. Based on this result it is proposed to study possible changes of models as a future development. Then the simulating program is created to illustrate features of examined automata.
|
guest ::
